Address generation has been a continuing problem for computers, particularly as operation speeds have increased. As the number and range of applications has expanded, there has arisen a need for address generators to produce a range of non-sequential address sequences. A common example is the bit- reversed addressing for the FFT.
Common Digital Signal Processing (DSP) addressing patterns include:
Sequential PA1 Inverted PA1 Reflected PA1 Bit-reversed PA1 Perfect shuffled (Interleaved) PA1 Multiple shuffled PA1 Parallel shuffled PA1 storage means for storing at least four descriptors representative of a matrix structure, wherein, PA1 at least two size descriptors representative of the size of two dimensions of an n-dimensional matrix and PA1 at least a further two of said descriptors are difference descriptors representative of the values of two finite address differences, PA1 a counter means per size descriptor, PA1 a sequential N-dimensional finite difference calculation means having as input said difference descriptors and an initially zero previously calculated output address from the address generator whereby said counter means controls the finite difference used by the calculation means to calculate a calculation means output address which is also the address generator output address of an element of an N-dimensional matrix. PA1 subtraction means for subtraction from said calculation means output address said modulo descriptor to produce a modulo subtraction means result and a subtraction means sign output, PA1 selection means to select as the output of said address generator either of the calculation means output address or the subtraction means output address according to the subtraction means sign output.
These patterns are in common usage as a result of the vector nature of the common computer architectures. Reference can be made to the paper by ZOBEL, R. N., "Some alternative techniques for hardware address generators for digital signal processors", ISCAS'88, CH2458-8/88 pp. 69-72, 1988, for a description of hardware which implements these addressing patterns. Another paper which describes a versatile hardware address indexing unit is by NWACHUKWU, E. O., "Address generation in an array processor", IEEE Trans. on Computers, Vol. C-34, No. 2, pp. 170-173, February 1985. A further paper which in part describes a general purpose address generation technique is the paper by HALL, F. E. and ROCCO Jr., A. G., "A compact programmable array processor", The Lincoln Laboratory Journal, Volume 2, Number 1, 1989.
In all of these papers the address generation techniques are designed to optimise vector-based algorithms. Matrices and matrix algorithms are supported as operations upon sets of vectors. These approaches have limitations when matrix algorithms are implemented which can not readily be expressed in terms of sets of vectors. An example of such an algorithm is the one-dimensional Fourier transform implemented with the prime factor algorithm.
The object of this invention is the provision of an address generator which is optimised for general matrix algorithms and which is capable of applying `on-the-fly` number theory mappings to matrix operands as they are fetched from memory.